package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/is-graph-bipartite/
 */
public class Title785 {

    private static boolean valid;
    private static final int UNCOLORED = -1;
    private static final int RED = 0;
    private static final int GREEN = 1;

    public static boolean isBipartite(int[][] graph) {
        //分成两个队伍0, 1,初始化-1
        int[] team = new int[graph.length];
        Arrays.fill(team, UNCOLORED);
        valid = true;
        //循环是判定从有边的节点开始，无边的节点染成红色
        for (int i = 0; i < graph.length; i++) {
            if (team[i] == UNCOLORED) {
                dfs(graph, team, i, RED);
            }
        }
        return valid;
    }

    private static void dfs(int[][] graph, int[] team, int cur, int teamNum) {
        team[cur] = teamNum;
        int reTeam = teamNum == RED ? GREEN : RED;
        for (Integer node : graph[cur]) {
            //未访问过的节点
            if (team[node] == UNCOLORED) {
                dfs(graph, team, node, reTeam);
                if (!valid) {
                    return;
                }
                //访问过的节点判断颜色
            } else if (team[node] == teamNum) {
                valid = false;
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{1,3},{0,2},{1,3},{0,2}};
        isBipartite(graph);
    }
}
